package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/find-champion-i/'>找到冠军 I(Find Champion I)</a>
 * <p>一场比赛中共有 n 支队伍，按从 0 到  n - 1 编号。</p>
 * <p>给你一个下标从 0 开始、大小为 n * n 的二维布尔矩阵 grid 。对于满足 0 <= i, j <= n - 1 且 i != j 的所有 i, j ：如果 grid[i][j] == 1，那么 i 队比 j 队 强 ；否则，j 队比 i 队 强 。</p>
 * <p>在这场比赛中，如果不存在某支强于 a 队的队伍，则认为 a 队将会是 冠军 。</p>
 * <p>返回这场比赛中将会成为冠军的队伍。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：grid = [[0,1],[0,0]]
 *      输出：0
 *      解释：比赛中有两支队伍。
 *          grid[0][1] == 1 表示 0 队比 1 队强。所以 0 队是冠军。
 *
 * 示例 2：
 *      输入：grid = [[0,0,1],[1,0,1],[0,0,0]]
 *      输出：1
 *      解释：比赛中有三支队伍。
 *          grid[1][0] == 1 表示 1 队比 0 队强。
 *          grid[1][2] == 1 表示 1 队比 2 队强。
 *          所以 1 队是冠军。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>n == grid.length</li>
 *     <li>n == grid[i].length</li>
 *     <li>2 <= n <= 100</li>
 *     <li>grid[i][j] 的值为 0 或 1</li>
 *     <li>对于所有 i， grid[i][i] 等于 0.</li>
 *     <li>对于满足 i != j 的所有 i, j ，grid[i][j] != grid[j][i] 均成立</li>
 *     <li>生成的输入满足：如果 a 队比 b 队强，b 队比 c 队强，那么 a 队比 c 队强</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/4/26 11:06
 */
public class LC2923FindChampion_I_S {

    static class Solution {
        public int findChampion(int[][] grid) {
            for (int col = 0; col < grid.length; col++) {
                boolean flag = false;
                for (int row = 0; row < grid[col].length; row++) {
                    // 如果当前列的每一行都是0，说明该队伍没输过，一定为冠军
                    if (grid[row][col] == 1) {
                        flag = true;
                        break;
                    }
                }
                if (!flag) {
                    return col;
                }
            }
            return -1;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.findChampion(
                new int[][]{
                        {0, 1},
                        {0, 0}
                }
        ));
        System.out.println(solution.findChampion(
                new int[][]{
                        {0, 0, 1},
                        {1, 0, 1},
                        {0, 0, 0,}
                }
        ));
    }
}
